package com.cat.greedyAlgorithm;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/
 * @create 2025/8/23 09:27
 * @since JDK17
 */

public class Solution18 {
    public int f1(int[] nums, int x) {
        int p1 = -1, p2 = x, n = nums.length, flag = 0;
        for (int num : nums) {
            if (num % 3 == 1) {
                p1 = x - num;
                break;
            }
        }
        for (int num : nums) {
            if (num % 3 == 2) {
                p2 -= num;
                flag++;
            }
            if (flag == 2) {
                break;
            }
        }
        if (flag != 2) {
            p2 = -1;
        }
        return Math.max(p1, p2);
    }

    public int f2(int[] nums, int x) {
        int p1 = -1, p2 = x, n = nums.length, flag = 0;
        for (int num : nums) {
            if (num % 3 == 2) {
                p1 = x - num;
                break;
            }
        }
        for (int num : nums) {
            if (num % 3 == 1) {
                p2 -= num;
                flag++;
            }
            if (flag == 2) {
                break;
            }
        }
        if (flag != 2) {
            p2 = -1;
        }
        return Math.max(p1, p2);
    }


    public int maxSumDivThree(int[] nums) {
        int ans = 0, n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            ans += nums[i];
        }
        if (ans % 3 == 0) {
            return ans;
        } else if (ans % 3 == 1) {
            return f1(nums, ans);
        } else {
            return f2(nums, ans);
        }
    }
}
